package leetcode31_40;

import org.junit.Test;

import java.util.Stack;

/**
 * @author shhjiang_001
 * @create 2020-06-15 19:29
 */

        /*
        给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
        示例 1:

        输入: "(()"
        输出: 2
        解释: 最长有效括号子串为 "()"
        */

public class Solution32 {

    public int longestValidParentheses(String s) {
        char[] arr = s.toCharArray();
        int res = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0;i< arr.length;i++){
            if (arr[i]=='('){
                stack.push(i);
            }else if (!stack.isEmpty()){
                arr[i] = '0';
                arr[stack.pop()] = '0';
            }
        }

        int le = 0;
        int ri = 0;
        while (ri < arr.length){
            if (arr[ri] == '0'){
                if (ri >= 1 && arr[ri-1] != '0'){
                    le = ri;
                    ri++;
                }else {
                    ri++;
                    res = Math.max(res,ri-le);
                }
            }else{
                ri++;
            }

        }
        return res;
    }
    public int longestValidParentheses1(String s) {
        Stack<Integer> stack = new Stack<>();
        int res = 0;
        stack.push(-1);
        for (int i = 0;i < s.length(); i++){
            if (s.charAt(i) == '('){
                stack.push(i);
            }else {
                stack.pop();
                if (stack.isEmpty()){
                    stack.push(i);
                }else {
                    res = Math.max(res,i-stack.peek());
                }
            }
        }
        return res;
    }
    @Test
    public void test() {
        Solution32 solution32 = new Solution32();
        int i = solution32.longestValidParentheses("(()())()()()(");
        System.out.println(i);
    }
}
